package leecode.二分法;

import java.util.Arrays;

public class 寻找第K小的距离对 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int i = solution.smallestDistancePair(new int[]{1, 3, 1, 4, 6, 5}, 3);
        System.out.println(i);
    }

    static class Solution {
        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int len=nums.length;
            int low=0;
            int high=nums[len-1]-nums[0];

            while(low<high){
                int mid=low+(high-low)/2;
                int count=0;
                int left=0;
                for(int right=0; right<len; right++){
                    while(nums[right]-nums[left]>mid) left++;
                    count+=right-left;
                }

                if(count>=k){
                    high=mid;
                }else{
                    low=mid+1;
                }
            }
            return low;
        }
    }


}
